package pl.vojna.ant_alg.lokal_search_alg;

import java.util.HashMap;

import pl.vojna.ant_alg.LocalSearch;
import pl.vojna.ant_alg.Problem;
import pl.vojna.ant_alg.Solution;
import pl.vojna.ant_alg.Utils;

public class TabuSearch implements LocalSearch {
	private static final int EMPTY = 1;
	private HashMap<Integer/* hash */, Solution> tabu = new HashMap<Integer, Solution>();

	@Override
	public int[] improve(int[] s, Problem problem, int iterations) {
		tabu.clear();
		int problemSize = problem.getSize();
		Solution solution = new Solution(problem, s);
		int bestDiff = 0, lastDiff = 0;
		int bestA = -1, bestB = -1;
		int lastA = -1, lastB = -1;

		lastDiff = Utils.swapFacilitiesCostDiff(problem, solution.getArray(),
				0, 1);
		lastA = 0;
		lastB = 1;
		solution.swap(0, 1);

		for (int i = 0; i < iterations; i++) {
			// w kazdym kroku szukamy takiego swap(a,b) by spadek kosztu byl jak
			// najwiekszy
			bestDiff = Integer.MAX_VALUE;
			for (int a = 0; a < problemSize; a++) {
				for (int b = 0; b < a; b++) {
					// tymczasowa zamiana elementow by sprawdzic czy permutacja
					// nie jest tabu
					solution.swap(a, b);
					int hash = solution.hashCode();
					solution.swap(a, b);
					if (tabu.containsKey(hash))
						continue;
					// obliczamy roznice kosztu dotychczasowego rozwiazania z
					// permutacja po podmianie
					// na pozycjach a , b
					int diff = 0;

					// diff = Utils.swapFacilitiesCostDiff(problem,
					// solution.getArray(), lastA, lastB, a, b, lastDiff);
					diff = Utils.swapFacilitiesCostDiff(problem,
							solution.getArray(), a, b);

					if (diff < bestDiff) {
						bestDiff = diff;
						bestA = a;
						bestB = b;
					}
				}
			}
			if (bestDiff < 0 || tabu.containsKey(solution.hashCode())) {
				lastDiff = bestDiff;
				lastA = bestA;
				lastB = bestB;
				solution.swap(bestA, bestB);
			} else {
				tabu.put(solution.hashCode(), solution.clone_());
			}
		}
		// wyszukiwanie najlepszego
		for (Solution tmp : tabu.values()) {
			if (tmp.getCost() < solution.getCost()) {
				solution = tmp;
			}
		}
		return solution.getArray();
	}

}
